/* 图的边表 */

const int MaxVertex = 10; //图中最多顶点数

const int MaxEdge = 100; //图中最多边数

// 边表
template <typename DataType>
class EdgeGraph
{
public:
    EdgeGraph(DataType a[ ]， int n, int e); //构造函数
    ~EdgeGraph (); //析构函数
    void Kruskal(); //Kruskal算法求最小生成树
private:
    int FindRoot(int parent[]， int v); //求顶点v所在集合的根
    DataType vertex[MaxVertex];    //存储顶点的一维数组
    EdgeType edge[MaxEdge];        //存储边的边集数组
    int vertexNum, edgeNum;         // 最大顶点数和边数
};

template <typename DataType>
void EdgeGraph<DataType>::Kruskal()
{
    int num  = 0, i , vertex1, vertex2;
    int parent[vertexNum];
    for(i = 0; i < vertexNum ; i++)
    parent[i]=-1;   //初始化n个连通分量
    for(num=0,i=0; num < vertexNum-1; i++)//依次考察最短边
    {
        vertex1 = FindRoot(parent, edge[i].from);
        vertex2 = FindRoot(parent, edge[i].to);
        if (vertex1 != vertex2)  //位于不同的集合
        {
            std::cout << "(" << edge[i]. from << " " << edge[i].to << ")" << edge[i].weight;
            parent[vertex2] =  vertex1;    //合并集合
            num++;
        }
    }
}

int FindRoot(int parent [],int v) //求顶点v所在集合的根
{
    int t= v;
    while (parent [t] >-1) //求顶点t的双亲一直到根
        t = parent[t];
    return t; 
}